/*
 * @lc app=leetcode.cn id=560 lang=javascript
 *
 * [560] 和为K的子数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let map  = new Map();
    map.set(0,1);
    let sum = 0;
    let res = 0;
    for(let i=0;i<nums.length;i++){
      sum += nums[i];
      if(map.has(sum-k))res += map.get(sum-k);
      map.set(sum,map.has(sum)?map.get(sum)+1:1);
    }
    return res
};
// @lc code=end
subarraySum([1,1,1,1],2)
var subarraySum = function(nums, k) {
    let dp=new Array(nums.length).fill(0).map((item)=>[])
    let count=0
    dp[0][0]=nums[0]
    if(nums[0]===k)count++
    for(let i=1;i<nums.length;i++){
        for(let j=0;j<=i;j++){
            dp[i][j]=((dp[i-1][j]?dp[i-1][j]:0)+nums[i])
            if(dp[i][j]===k)count++
        }
    }
    return count
};//内存爆了
var subarraySum = function(nums, k) {
    
    let count = 0;
    for (let start = 0; start < nums.length; ++start) {
        let sum = 0;
        for (let end = start; end >= 0; --end) {
            sum += nums[end];
            if (sum == k) {
                count++;
            }
        }
    }
    return count;
};//超时，思路和我DP一致的